With submicron technology, large numbers of processors, elements, or devices can be integrated on microcircuit chips. The processors, elements, or devices are arranged in arrays of cells on one or more layers of a chip. Each of the cells, containing a component of one or more overall circuits, contains one or more terminals for communicating with other cells. To permit the cells to communicate with one another interconnects, such as routing wires or other conductive paths, connect the cells and/or bus segments, which themselves interconnect groups of cells.
The interconnects are arranged in meshes formed in or among one or more interconnect layers (also known as routing layers) of a microcircuit chip. A mesh is a common routing architecture for many reconfigurable computing systems. Both conventional and more recently proposed on-chip multiprocessor systems use mesh networks as communication backbones.
The microcircuit chips typically include a plurality of interconnect layers for interconnection of the cells. Pluralities of layers are often used for individual interconnections due to design constraints, for example. Vias help to route the interconnects between pluralities of layers. Connections are switched by devices such as, but not limited to, metal oxide semiconductor (MOS) devices.
High-performance system-on-a-chip (SoC) requires nonblocking interconnects between the array of cells on the chip. With nonblocking interconnects, when a cell needs to communicate with another cell, a route always exists for communication.
Interconnects have become one of the most precious resources on a chip. Length of connection between cells is a limiting performance factor in terms of power consumption and latency, among other factors. Unreasonable distribution of interconnect resources results in bottlenecks that stall data flow, while leaving other routing resources wasted. Furthermore, it is impractical to resolve this problem merely by enlarging a channel capacity of an entire array.
A long path through interconnects increases power consumption and signal delay. Additionally, a common physical embodiment of multiprocessor arrays is CMOS technology. In CMOS technology, power dissipation is proportional to interconnect capacitance, which in turn is proportional to a distance traveled by a signal. Thus, it is highly desirable to provide an architecture in which interconnection length is minimized. It is also desirable to provide an architecture that includes the shortest totals of route lengths between processors, and not interconnect length alone.
One predominant type of interconnect mesh is Manhattan architecture, so-called because its rectilinear connection arrangement resembles a city street grid. Manhattan architecture, however, requires lengths of interconnects that far exceed actual (Euclidean) distances between individual cells due to, for example, the requirement for orthogonal circuit paths.
More recently, an alternative chip architecture known as X-architecture has been introduced to reduce interconnection lengths versus Manhattan architecture. X-architecture uses tree structures having recursive patterns to interconnect cells in a nonblocking interconnection architecture. The tree structures may take the form of H-shaped patterns or X-shaped patterns, with the cells located at the extremities of each pattern. The interconnects are oriented, for example, in 0°, 45°, 90°, and 135° directions. X-architecture has been disclosed as a solution to address microcircuit chip designs, especially chips with five or more routing layers.
Interconnection between all cells is provided by a specific hierarchical structure. For example, at a level “zero”, four cells may be interconnected by an “X”. At a higher level, say, level “1”, four level “zero” “X's” are interconnected by a larger “X”. At a still-higher level (“2”), four level “1” “X's” are interconnected by a still-larger “X”, etc. Performance improvement of the X-architecture over the Manhattan architecture has been demonstrated.